package onlinebanking.security.threshold;

import onlinebanking.math.Rational;
import java.math.BigInteger;

public class KeyRetriever {

	public int[] interpolate(int[][] sharepairs) {
		Share[] shares = new Share[sharepairs.length];
		for (int i = 0; i < shares.length; i++) {
			shares[i] = new Share(sharepairs[i][0], sharepairs[i][1]);
		}
		Rational[] rcoeffs = interpolate(shares);
		int[] coeffs = new int[rcoeffs.length];
		for (int i = 0; i < coeffs.length; i++) {
			coeffs[rcoeffs.length - i - 1] = (int) rcoeffs[i].evaluate();
		}

		return coeffs;
	}

	/**
	 * polynomial interpolation using the Lagrange Method
	 */
	public Rational[] interpolate(Share[] shares) {
		int denominator = 0;
		Rational[] result = null;
		Rational[][] lagrangeBasis = new Rational[shares.length][];
		Rational[] initialCoeff = null;
		Rational[] newCoeff = null;

		for (int i = 0; i < shares.length; i++) {
			denominator = 1;
			initialCoeff = new Rational[1];
			initialCoeff[0] = new Rational(1, 1);

			// generate the lagrange basis polynomials
			for (int j = 0; j < shares.length; j++) {
				if (j != i) {
					int newLength = initialCoeff.length + 1; // create a
																// polynomial of
																// size n + 1
					newCoeff = new Rational[newLength];

					// the idea here is that f(x)(x - b) = f(x)x + f(x)(-b);

					// multiply the old polynomial by x and add it to the new
					// polynomial
					// in other words, compute for f(x)x
					int k = newCoeff.length - 1;
					for (int l = initialCoeff.length - 1; l >= 0; l--, k--) {
						newCoeff[k] = initialCoeff[l];// copy the contents of
														// the old array to the
														// new array by one
														// index higher
					}

					for (int l = 0; l <= k; l++) { // pad the remainder with
													// zeros
						newCoeff[l] = new Rational(0, 1);
					}

					// multiply the old polynomial by -b and add it the the new
					// polynomial
					// in other words, compute for f(x)(-b) and add the result
					// on the previous polynomial
					for (int l = initialCoeff.length - 1; l >= 0; l--) {
						// newCoeff[l] =
						// newCoeff[l].add(initialCoeff[l].getNumerator().multiply(new
						// BigInteger(String.valueOf(shares[j].getX())).multiply(new
						// BigInteger(String.valueOf("-1"))), BigInteger.ONE);
						// initialCoeff[l].numerator * shares[j].getX() * -1,
						// 1);

						newCoeff[l] = newCoeff[l].add(
								initialCoeff[l]
										.getNumerator()
										.multiply(
												new BigInteger(String
														.valueOf(shares[j]
																.getX())))
										.multiply(
												new BigInteger(String
														.valueOf("-1"))),
								BigInteger.ONE);
					}
					initialCoeff = newCoeff;
					denominator *= (shares[i].getX() - shares[j].getX());
				}

			}

			for (int j = 0; j < shares.length; j++) {
				initialCoeff[j] = initialCoeff[j].divide(denominator, 1);
			}

			lagrangeBasis[i] = initialCoeff;
		}

		// get the resulting polynomial from the lagrange basis polynomials

		// initialize the resulting polynomial
		result = new Rational[shares.length];
		for (int i = 0; i < result.length; i++) {
			result[i] = new Rational(0, 1);
		}

		//
		for (int i = 0; i < lagrangeBasis.length; i++) {
			for (int j = 0; j < lagrangeBasis[i].length; j++) {
//				result[j] = result[j].add(lagrangeBasis[i][j].numerator
//						* shares[i].getY(), lagrangeBasis[i][j].denominator);
				
				result[j] = result[j].add(lagrangeBasis[i][j].getNumerator().multiply(new BigInteger(String.valueOf(shares[i].getY()))), lagrangeBasis[i][j].getDenominator());
			
			}
		}

		// print the coefficients of the resulting polynomial
		for (int i = 0; i < result.length; i++) {
			System.out.println(result[i] + " = " + result[i].evaluate());
		}

		return result;
	}

	public static void main(String[] args) {
		System.out.println("Key Retriver started.");

		KeyRetriever k = new KeyRetriever();
		// Generating random polynomial with degree 3 and 99 as constant...
		// -5x^3 + -8x^2 + 6x + 99
		// Generating 5 shares...
		// ( 1 , 92 )
		// ( 2 , 39 )
		// ( 3 , -90 )
		// ( 4 , -325 )
		// ( -11 , 5720 )

		int s[][] = { { 1, 92 }, { 2, 39 }, { 3, -90 }, { 4, -325 },
				{ -11, 5720 } };

		int rats[] = k.interpolate(s);

		for (int i = 0; i < rats.length; i++) {

			System.out.println(rats[i]);
		}
	}

	public Share[] generatesample() {
		Share a, b, c, d, e;
		a = new Share(1, 92);
		b = new Share(2, 39);
		c = new Share(3, -90);
		d = new Share(4, -325);
		e = new Share(-11, 5720);
		Share s[] = { a, b, c, d, e };
		return s;
	}
}
